package com.samxcode.nio;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

/**
 * 提升hashmap的rehash过程
 * 
 * @author Sam
 *
 * @param <K>
 * @param <V>
 */
public class ProHashMap<K, V> {

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified by either of the
     * constructors with arguments. MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    static class Node<K, V> implements Map.Entry<K, V> {

        final int hash;
        final K key;
        V value;
        Node<K, V> next;


        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }


        public final K getKey() {
            return key;
        }


        public final V getValue() {
            return value;
        }


        public final String toString() {
            return key + "=" + value;
        }


        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }


        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }


        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?, ?> e = (Map.Entry<?, ?>) o;
                if (Objects.equals(key, e.getKey())
                        && Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }


    static int hash(Object key) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    Node<K, V>[] table;

    Node<K, V>[] newTable;

    int rehashFlag; // 0表示正常阶段，1表示rehash阶段

    int size;

    int newSize; // newTable的大小

    int transNum = 0; // 已经rehash的table元素个数

    int modCount;

    int threshold = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

    final float loadFactor;


    @SuppressWarnings("unchecked")
    public ProHashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
        table = (Node<K, V>[]) new Node[DEFAULT_INITIAL_CAPACITY];
    }


    public V put(K key, V value) {
        V resVal = null;
        int hash = hash(key);
        if (rehashFlag == 0) {
            resVal = putVal(table, hash, key, value);
            if (size + 1 > threshold) // 如果size达到阀值，进入rehash阶段
                rehash();
        } else {
            // 如果对应元素仍然存在于原table，将node链表rehash到newTable
            if (isExist(hash, key)) {
                resVal = rehash(hash, key, value);
                transNum++;
            }
            // 将值放入newTable中
            resVal = putVal(newTable, hash, key, value);
            if (resVal == null) {
                newSize++;
            }
            // 判断rehash完成
            if (transNum == table.length || newSize >= threshold
                    || size >= threshold) {
                newSize = 0;
                rehashFlag = 0;
                transNum = 0;
                table = newTable;
            }
        }
        return resVal;
    }


//    private void transfer() {
//        Node<K, V>[] oldTab = table;
//        Node<K, V>[] newTab = newTable;
//        Node<K, V> e;
//        int oldCap = table.length;
//        for (int j = 0; j < oldCap; j++) {
//            if (oldTab[j] != null) {
//                e = oldTab[j];
//                oldTab[j] = null;
//                Node<K, V> loHead = null, loTail = null;
//                Node<K, V> hiHead = null, hiTail = null;
//                Node<K, V> next;
//                do {
//                    next = e.next;
//                    if ((e.hash & oldCap) == 0) {
//                        if (loTail == null)
//                            loHead = e;
//                        else
//                            loTail.next = e;
//                        loTail = e;
//                    } else {
//                        if (hiTail == null)
//                            hiHead = e;
//                        else
//                            hiTail.next = e;
//                        hiTail = e;
//                    }
//                    newSize++;
//                } while ((e = next) != null);
//                if (loTail != null) {
//                    loTail.next = null;
//                    newTab[j] = loHead;
//                }
//                if (hiTail != null) {
//                    hiTail.next = null;
//                    newTab[j + oldCap] = hiHead;
//                }
//            }
//        }
//    }


    // rehash链表
    private V rehash(int hash, K key, V value) {
        // System.out.println("rehash");
        Node<K, V>[] oldTab = table;
        Node<K, V>[] newTab = newTable;
        Node<K, V> e;
        int j;
        int oldCap = table.length;
        if (oldTab[j = (oldCap - 1) & hash] != null) {
            e = oldTab[j];
            oldTab[j] = null;
            Node<K, V> loHead = null, loTail = null;
            Node<K, V> hiHead = null, hiTail = null;
            Node<K, V> next;
            do {
                next = e.next;
                if ((e.hash & oldCap) == 0) {
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                } else {
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
                newSize++;
            } while ((e = next) != null);
            if (loTail != null) {
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) {
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
        return null;
    }


    @SuppressWarnings("unchecked")
    private void rehash() {
        Node<K, V>[] oldTab = table;
        int oldCap = oldTab == null ? 0 : table.length;
        int newCap = oldCap == 0 ? DEFAULT_INITIAL_CAPACITY : oldCap << 1;
        int oldThr = threshold;
        int newThr = oldThr << 1;
        threshold = newThr;
        newTable = (Node<K, V>[]) new Node[newCap];
        rehashFlag = 1;
    }


    // 判断hash取余之后table相应的index是否还有元素，即该链表是否已经rehash
    final boolean isExist(int hash, K key) {
        Node<K, V>[] tab = table;
        int n;
        if (tab != null && (n = tab.length) != 0 && tab[(n - 1) & hash] != null) {
            return true;
        }
        return false;
    }


    /**
     * Implements Map.put and related methods
     *
     * @param hash
     *            hash for key
     * @param key
     *            the key
     * @param value
     *            the value to put
     * @param onlyIfAbsent
     *            if true, don't change existing value
     * @param evict
     *            if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(Node<K, V>[] tab, int hash, K key, V value) {
        Node<K, V> p;
        int n, i;
        if (tab == null || (n = tab.length) == 0)
            n = tab.length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K, V> e;
            K k;
            if (p.hash == hash
                    && ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else {
                for (;;) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        break;
                    }
                    if (e.hash == hash
                            && ((k = e.key) == key || (key != null && key
                                .equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (oldValue == null)
                    e.value = value;
                return oldValue;
            }
        }
        ++size;
        return null;
    }


    Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node<>(hash, key, value, next);
    }


    public static void main(String[] args) {
        ProHashMap<Integer, Integer> map = new ProHashMap<>();
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < 3000000; i++) {
            Long l = System.currentTimeMillis();
            map.put(i, 1000000);
            Long l1 = System.currentTimeMillis();
            if (l1 - l > 1) {
                System.out.println(i + " ProHashMap: " + (l1 - l));
            }
            hashMap.put(i, 1000000);
            Long l2 = System.currentTimeMillis();
            if (l2 - l1 > 1) {
                System.out.println(i + " hashmap: " + (l2 - l1));
            }
        }
        System.out.println("程序运行完成");
    }
}
